package games.graphPath;

import games.graphPath.Graph.Edge;
import games.graphPath.Graph.Vertex;
import genetics.DescendantCreator;
import genetics.GeneticInterface;

import java.util.*; 

public class GraphPathGenticSearch{

	private static int INITIAL_PATHS = 100;
	
	private Graph _graph;
	
	private int _maxDepth;
	
	public GraphPathGenticSearch(Graph g, int maxDepth){
		_graph = g;
		_maxDepth = maxDepth;
	}

	public void search(GraphPathResult r)
	{
		search(r,INITIAL_PATHS);
	}
	
	
	//public GraphPathResult serch(int numPaths)
	public void search(GraphPathResult r, int numPaths)
	{
		long beginTime1 = System.currentTimeMillis();
		
		DescendantCreator<GeneticVertex> dc = new DescendantCreator<GeneticVertex>();
		
		List<ArrayList<GeneticVertex>> possiblePaths = getPossiblePaths(numPaths);
		if (possiblePaths==null || possiblePaths.size()==0)
		{
			r.addFailed(GraphPathResult.GENETIC);
			return;
		}	
		
		long beginTime2 = System.currentTimeMillis();
		int depth = 0;
		while (possiblePaths.size()>1 )
		{
			depth++;
			int count = possiblePaths.size();
			for (int i=0; i<count-1; i+=2)
			{
				ArrayList<GeneticVertex> father = possiblePaths.remove(0);
				ArrayList<GeneticVertex> mother = possiblePaths.remove(0);
				possiblePaths.add(dc.generateDescendant(father, mother));
			}
			 
		}
		
		long time = System.currentTimeMillis() - beginTime2;
		long buildTime = beginTime2-beginTime1;
		
		r.add(GraphPathResult.GENETIC,possiblePaths.get(0),time, buildTime);
			
	}


	private List<ArrayList<GeneticVertex>> getPossiblePaths(int numPaths)
	{
		ArrayList<ArrayList<GeneticVertex>> toReturn = new ArrayList<ArrayList<GeneticVertex>>();

		//build random paths from src to dest
		Random r = new Random();
		for (int i=0; i<numPaths; i++)
		{
			Vertex curVertex = _graph.getSrc();
			int depth = 0;
			ArrayList<GeneticVertex> list = new ArrayList<GeneticVertex>();
			while (curVertex.getIndex()!=_graph.getDst().getIndex() && depth<_maxDepth)
			{
				List<Edge> out = curVertex.getOutNeighbors();
				depth++;
				if (out==null || out.size()==0)
				{
					break;
				}
				Edge curEdge = out.get(r.nextInt(out.size()));
				curVertex = curEdge.getDst();
				list.add(new GeneticVertex(curEdge));
			}
			if (curVertex.getIndex()==_graph.getDst().getIndex())
			{
				toReturn.add(list);
			}
		}
		
		return toReturn;
	}
	
		
	public class GeneticVertex implements GeneticInterface
	{
		private String _hash;
		private int _weight;
		private Vertex _vertex;
		
		public GeneticVertex(Edge edge)
		{
			_vertex = edge.getDst();
			_hash = String.valueOf(_vertex.getIndex());
			_weight = edge.getCost();
		}
		
		public String hash()
		{
			return _hash;
		}
		
		public int weight()
		{
			return _weight;
		}

		public Vertex getVertex() {
			return _vertex;
		}
	}



}
